|
|
Visualization of Longest Prefix Match Algorithms
Fomiczew, Jiří ; Matoušek, Jiří (referee) ; Kováčik, Michal (advisor)
This thesis describes the design and implementation of program for vizualization of algorithms for longest pre fix match (LPM), which is one of the most important tasks for packet classi cation and routing in TCP/IP networks. It describes necessary theory and details about selected algorithms - Trie, Tree Bitmap and CPE. Furthermore, it describes the design and implementation of program for vizualization of the search process of these algorithms with emphasis on the potential use for educational purposes. Finally, it describes the possibilities for future development and expansion of the program.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Matoušek, Jiří (referee) ; Tobola, Jiří (advisor)
This master's thesis explains basics of the longest prefix match (LPM) problem. It analyzes and describes chosen LPM algorithms considering their speed, memory requirements and an ability to implement them in hardware. On the basis of former findings it proposes a new algorithm Generic Hash Tree Bitmap. It is much faster than many other approaches, while its memory requirements are even lower. An implementation of the proposed algorithm has become a part of the Netbench library.
|
|
|
Graphical Demonstration of Selected Route Lookup Algorithm
Olejník, Tomáš ; Kaštil, Jan (referee) ; Puš, Viktor (advisor)
This thesis briefly describes principe of networks, routing protocols and there are described basis of some existing longest prefix match algorithms, which are implemented in router's hardware. Main part of thesis deals with a Tree Bitmap algorithm, that demonstration program creating is an objective of this work. The principe of this algorithm is demonstrated by visual animations.
|
|
|
Longest Prefix Match Algorithms
Skačan, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with the algorithms for longest prefix match (LPM), which is the basic operation of the packet classification and of the routing in the IP computer networks. It is introduced the necessary theory and the analysis of the chosen algorithms - Trie, Tree Bitmap, Shape Shifting Tree and Multi-match. These methods were closely described and they were implemented in the programming language Python. Within the implemented algorithms were performed tests and simulations considering their memory demands with the aim to identify the best method for prefix collections about the size of tens to thousands rules.
|
|
| |
|
|
Longest Prefix Match Algorithms
Skačan, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with the algorithms for longest prefix match (LPM), which is the basic operation of the packet classification and of the routing in the IP computer networks. It is introduced the necessary theory and the analysis of the chosen algorithms - Trie, Tree Bitmap, Shape Shifting Tree and Multi-match. These methods were closely described and they were implemented in the programming language Python. Within the implemented algorithms were performed tests and simulations considering their memory demands with the aim to identify the best method for prefix collections about the size of tens to thousands rules.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
|
|
|
Visualization of Longest Prefix Match Algorithms
Fomiczew, Jiří ; Matoušek, Jiří (referee) ; Kováčik, Michal (advisor)
This thesis describes the design and implementation of program for vizualization of algorithms for longest pre fix match (LPM), which is one of the most important tasks for packet classi cation and routing in TCP/IP networks. It describes necessary theory and details about selected algorithms - Trie, Tree Bitmap and CPE. Furthermore, it describes the design and implementation of program for vizualization of the search process of these algorithms with emphasis on the potential use for educational purposes. Finally, it describes the possibilities for future development and expansion of the program.
|
|
|
Graphical Demonstration of Selected Route Lookup Algorithm
Olejník, Tomáš ; Kaštil, Jan (referee) ; Puš, Viktor (advisor)
This thesis briefly describes principe of networks, routing protocols and there are described basis of some existing longest prefix match algorithms, which are implemented in router's hardware. Main part of thesis deals with a Tree Bitmap algorithm, that demonstration program creating is an objective of this work. The principe of this algorithm is demonstrated by visual animations.
|
guest ::
